/**
 * vue diff 算法
 * @param {*} c1 老节点数组
 * @param {*} c2 新节点数据
 */
const patchKeyedChildren = (c1, c2, { patch, mount, unmount, move }) => {
  let i = 0; // 起始索引
  const l2 = c2.length; // 新节点数组长度
  let e1 = c1.length - 1; // 老节点数组结束索引
  let e2 = l2 - 1; // 新节点数组结束索引

  // 1. 从头部开始同步节点
  while (i <= e1 && i <= e2) {
    const n1 = c1[i];
    const n2 = c2[i];
    // 如果是相同节点，证明可以复用节点，执行patch操作
    if (isSameVNodeType(n1, n2)) {
      patch(n1.key, n2.key);
    } else {
      // 否则，中断循环
      break;
    }
    // 每有一个相同的节点，起始索引加1
    i++;
  }

  // 2. 从尾部开始同步节点
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1];
    const n2 = c2[e2];
    // 判断是相同节点则复用
    if (isSameVNodeType(n1, n2)) {
      patch(n1.key, n2.key);
    } else {
      break;
    }
    e1--;
    e2--;
  }

  // 3. 新节点还有，老节点没了
  if (i > e1) {
    if (i <= e2) {
      // 添加多出来的节点
      while (i <= e2) {
        mount(c2[i].key);
        i++;
      }
    }
  }
  // 4. 老节点还有，新节点没了
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i].key);
      i++;
    }
  }
  // 5. 处于中间的乱序节点
  // [i ... e1 + 1]: a b [c d e] f g
  // [i ... e2 + 1]: a b [e d c h] f g
  // i = 2, e1 = 4, e2 = 5
  else {
    const s1 = i; // 记录剩下老节点的起始位置
    const s2 = i; // 记录剩下新节点的起始位置

    // 5.1 将剩下未执行比较的新节点数组转map
    // key就是节点的key，value是新节点数组的index
    const keyToNewIndexMap = new Map();
    for (i = s2; i <= e2; i++) {
      const nextChild = c2[i];
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, i);
      }
    }

    // 5.2 遍历剩余老节点，把能处理的处理了（patch, unmout）
    let j;
    let patched = 0; // 记录已经patch的节点数量
    let toBePatched = e2 - s2 + 1; // 需要patch的数量，就是剩下所有的新节点的数量
    let moved = false; // 记录是否有节点移动
    let maxNewIndexSoFar = 0; // 记录最大的新节点索引，用于辅助判断是否有节点移动的
    // 用于记录剩下的节点是否有移动，索引是剩余新节点index（从0开始），值是老节点下标
    const newIndexToOldIndexMap = new Array(toBePatched);
    // 初始化为0
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

    // 变量剩下的老节点
    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i];
      // 如果已经没有需要patch的节点了，证明后面的节点都是要删除的，直接删除
      if (patched >= toBePatched) {
        unmount(prevChild.key);
        continue;
      }

      let newIndex; // 新节点数组的index
      if (prevChild.key != null) {
        // 如果有key，直接从map中获取index
        newIndex = keyToNewIndexMap.get(prevChild.key);
      } else {
        // 针对部分没有key的节点，遍历剩余新节点数组
        for (j = s2; j <= e2; j++) {
          if (
            newIndexToOldIndexMap[j - s2] === 0 && // 没有进行过patch
            isSameVNodeType(prevChild, c2[j]) // 是同一个节点
          ) {
            newIndex = j;
            break; // 找到就不用再遍历
          }
        }
      }

      // 如果找不到新节点的索引，证明老节点没法复用，删除
      if (newIndex === undefined) {
        unmount(prevChild.key);
      } else {
        // 每次找到可以复用的节点，设置值为老节点索引加1
        newIndexToOldIndexMap[newIndex - s2] = i + 1;
        // 记录新节点的索引，如果索引突然变小了，证明有节点的位置变了
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex; // 记录上一个移动的最大索引
        } else {
          moved = true;
        }
        // 可以复用，执行patch
        patch(prevChild.key, c2[newIndex].key);
        patched++; // 已patch的数量加1
      }
    }

    // 5.3 移动和新建
    // 获取最长递增子序列
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : [];
    j = increasingNewIndexSequence.length - 1;
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i; // i是相对坐标，要加上起始值，转为新节点真实坐标
      const nextChild = c2[nextIndex];
      // 如果没有进行patch操作，证明是新增节点
      if (newIndexToOldIndexMap[i] === 0) {
        mount(nextChild.key);
      } else if (moved) {
        // 如果没有稳定的子序列（e.g. 数组倒序）或者 当前节点不在稳定序列中，移动节点
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild.key);
        } else {
          j--;
        }
      }
    }
  }
};

/**
 * 获取最长递增子序列
 * https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97
 * @param {*} arr
 * @returns
 */
function getSequence(arr) {
  const p = arr.slice();
  const result = [0]; // 最少会有一个移动的
  let i, j, u, v, c;
  const len = arr.length;
  // 遍历数组
  for (i = 0; i < len; i++) {
    // 取出当前元素
    const arrI = arr[i];
    // 只看进行过patch的数据
    if (arrI !== 0) {
      // 取出结果数组最后一个元素
      j = result[result.length - 1];
      // 如果当前元素比最后一个元素要大
      if (arr[j] < arrI) {
        p[i] = j; // 替换结果数组中最后一个值
        result.push(i); // 将当前索引存入结果索引
        continue;
      }
      u = 0; // 结果起始索引
      v = result.length - 1; // 结果数组索引
      // 二分查找，在结果数组中找到当前值得位置
      while (u < v) {
        c = (u + v) >> 1; // 取中间值
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      // 将当前值替换到比它大一点的位置
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]; // 存起来
        }
        result[u] = i;
      }
    }
  }
  // 修正索引
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  return result;
}

/**
 * 判断两个节点是否相同
 * @param {*} n1
 * @param {*} n2
 * @returns
 */
function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key;
}

exports.patchKeyedChildren = patchKeyedChildren;
